/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM79 打家劫舍(二)
 * https://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815?tpId=295&tqId=2285837&ru=%2Fpractice%2Fc5fbf7325fbd4c0ea3d0c3ea6bc6cc79&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
 * User: DELL
 * Data: 2022-11-17
 * Time: 18:18
 */

//动态规划
//本题再动态规划（一）的基础上，讨论两种情况
//由于第一家和最后一家不能同时取到，因此分别
//讨论舍弃第一家和最后一家两种情况，取两种情况的较大值
import java.util.*;

public class Solution {
    public int rob (int[] num) {
        //题目中规定num数组不为空
        int len = num.length;
        //只有一家时
        if (len == 1) {
            return num[0];
        }
        //只有两家时
        if (len == 2) {
            return 0;
        }
        //dp[i]表示打劫前i家获得的最大的现金金额
        int[] dp = new int[len];
        //1.舍弃第一家
        dp[0] = 0;
        dp[1] = num[1];
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i-2] + num[i],dp[i-1]);
        }
        int tmp = num[len - 1]
        //舍弃最后一家
        dp[0] = num[0];
        dp[1] = Math.max(num[0],num[1]);
        for (int i = 2; i < len - 1; i++) {
            dp[i] = Math.max(dp[i-2] + num[i],dp[i-1]);
        }
        return Math.max(tmp,dp[len - 2]);
    }
}